Μη ντετερμινιστικό πεπερασμένο αυτόματο

Στη θεωρία υπολογισμού, το μη ντετερμινιστικό πεπερασμένο αυτόματο (αγγλικά: nondeterministic finite-state automaton (NFA)‎‎ ) είναι ένα πεπερασμένο αυτόματο που από μία κατάσταση, διαβάζοντας ένα σύμβολο εισόδου, μπορεί να μεταβεί σε μία ή και παραπάνω καταστάσεις, σε αντίθεση με το ντετερμινιστικό πεπερασμένο αυτόματο (DFA) που μπορεί να μεταβεί σε μία μόνο κατάσταση. Τα αυτόματα αυτά είναι πεπερασμένα, επειδή ο αριθμός των καταστάσεών τους είναι πεπερασμένος.

Τα μη ντετερμιστικά πεπερασμένα αυτόματα μπορούν να αναγνωρίσουν μόνο κανονικές γλώσσες, όπως και τα ντετερμινιστικά πεπερασμένα αυτόματα. Μάλιστα, για κάθε μη ντετερμινιστικό πεπερασμένο αυτόματο που αναγνωρίζει μια γλώσσα, υπάρχει ένα ισοδύναμο ντετερμινιστικό που αναγνωρίζει την ίδια γλώσσα.

Τα μη ντετερμιστικά πεπερασμένα αυτόματα εισήχθησαν το 1959 από τους Μάικλ Ο. Ράμπιν και Ντέινα Σκοτ.

Ορισμός

Ένα μη ντετερμινιστικό πεπερασμένο αυτόματο είναι μια πεντάδα (Q, Σ, δ, q₀, F) που αποτελείται από

• ένα πεπερασμένο σύνολο καταστάσεων Q
• ένα αλφάβητο εισόδου Σ
• μια συνάρτηση μετάβασης $\delta :Q\times \Sigma \rightarrow Pow(Q)$, όπου Pow(Q) είναι το δυναμοσύνολο του Q.
• μια αρχικής κατάσταση q₀ και
• ένα σύνολο τελικών καταστάσεων F, υποσύνολο του Q.

Πεπερασμένο σύνολο καταστάσεων

Πρόκειται για ένα σύνολο πεπερασμένων στον αριθμό καταστάσεων. Μία κατάσταση ενός μη ντετερμινιστικού πεπερασμένου αυτόματου οδηγεί σε ένα υποσύνολο καταστάσεων (το οποίο μπορεί να είναι και το κενό) από το σύνολο αυτό, ανάλογα με το σύμβολο εισόδου στο αυτόματο. Οι καταστάσεις διακρίνονται σε τελικές και μη τελικές. Τέλος, η αρχική κατάσταση q₀ είναι αυτή στην οποία βρίσκεται το αυτόματο αρχικά, δηλαδή πριν διαβάσει οποιαδήποτε είσοδο.

Αλφάβητο εισόδου

Είναι ένα σύνολο, Σ, από σύμβολα τα οποία διαβάζει το αυτόματο. Μέσω του συμβόλου που διαβάζει κάθε φορά και σύμφωνα με την συνάρτηση μετάβασης, δ, το αυτόματο κινείται μεταξύ των καταστάσεών του. Αν καταλήξει σε τουλάχιστον μία τελική κατάσταση, δηλαδή σε ένα υποσύνολο καταστάσεων που περιέχει τουλάχιστον μία τελική κατάσταση, τότε η ακολουθία των συμβόλων που διαβάστηκε από το αυτόματο γίνεται αποδεκτή.

Συνάρτηση μετάβασης

Η συνάρτηση μετάβασης είναι μια συνάρτηση με παραμέτρους μία κατάσταση και ένα σύμβολο εισόδου. Το πεδίο τιμών της είναι το δυναμοσύνολο του συνόλου, Q, των καταστάσεων, δηλαδή όλα τα δυνατά υποσύνολα του Q. Με άλλα λόγια, το αυτόματο, μπορεί από μία κατάσταση και με είσοδο ένα σύμβολο να μεταβεί σε παραπάνω από μία καταστάσεις. Μέσω της συνάρτησης μετάβασης καθορίζεται το πώς κινείται το αυτόματο σε κάθε περίπτωση, δηλαδή από κάθε κατάσταση με οποιοδήποτε σύμβολο από το αλφάβητο.

Η συνάρτηση μετάβασης μπορεί να επεκταθεί από τη $\delta :Q\times \Sigma \rightarrow Pow(Q)$ στη ${\tilde {\delta }}:Q\times \Sigma ^{*}\rightarrow Pow(Q)$, η οποία δέχεται ένα ζεύγος κατάστασης και συμβολοσειράς (αντί ενός συμβόλου μόνο) και το πεδίο τιμών της είναι πάλι το δυναμοσύνολο του Q. Δηλαδή, δεδομένης μιας αλφαβήτου Σ και ενός πεπερασμένου συνόλου καταστάσεων Q, αν $q_{1},q_{2}\in Q$ και $a,b\in \Sigma$, τότε η παράσταση ${\tilde {\delta }}(q_{1},ab)=q_{2}$ σημαίνει ότι αν το αυτόματο βρίσκεται στην κατάσταση q₁ και στη είσοδο διαβάσει τη συμβολοσειρά ab, τότε θα βρεθεί στην κατάσταση q₂. Ένας πιο αυστηρός αναδρομικός ορισμός είναι ο παρακάτω:

${\tilde {\delta }}:Q\times \Sigma ^{*}\rightarrow Pow(Q)$

${\tilde {\delta }}(q,\epsilon )=\{q\}$, όπου ε το κενό σύμβολο

${\tilde {\delta }}(q,wa)=\{p\in \delta (r,a)|r\in {\tilde {\delta }}(q,w)\}$, όπου $w\in \Sigma ^{*}$ συμβολοσειρά και $a\in \Sigma$ σύμβολο της αλφαβήτου.

Αυτή η νέα συνάρτηση μπορεί να επεκταθεί στην

${\overline {\delta }}:Pow(Q)\times \Sigma ^{*}\rightarrow \ Pow(Q)$

${\overline {\delta }}(P,w)=\{p\in {\tilde {\delta }}(q,w)|q\in P\}$, όπου $P\in Q$ ένα υποσύνολο καταστάσεων, $w\in \Sigma ^{*}$ μια συμβολοσειρά.

Η συνάρτηση αυτή, δέχεται ένα οποιοδήποτε υποσύνολο καταστάσεων από το Q και μια οποιαδήποτε συμβολοσειρά από το Σ*. Αυτή η επεκτεταμένη συνάρτηση μετάβασης δείχνει σε ποιες καταστάσεις θα καταλήξει το αυτόματο αν ξεκινήσει από κάποιες και διαβάσει μια ακολουθία συμβόλων. Μια τέτοια συνάρτηση μετάβασης βοηθάει στην κατανόηση των μη ντετερμινιστικών πεπερασμένων αυτόματων, αφού αυτά κινούνται όχι από κατάσταση σε κατάσταση, αλλά από πολλές καταστάσεις σε πολλές καταστάσεις. Έτσι, αντί να εφαρμόζουμε την δ για κάθε κατάσταση ξεχωριστά, εφαρμόζουμε την ${\overline {\delta }}$ για όλες τις καταστάσεις του υποσυνόλου μαζί.

Σύνολο τελικών καταστάσεων

Το σύνολο των τελικών καταστάσεων είναι ένα υποσύνολο του Q με την ιδιότητα αν καταλήξει σε τουλάχιστον μία τέτοια κατάσταση, η είσοδος να γίνεται αποδεκτή από το αυτόματο. Διαφορετικά, δηλαδή, αν το αυτόματο δεν καταλήξει σε καμία τελική κατάσταση, τότε η είσοδος απορρίπτεται.

Λειτουργία

Το μη ντετερμινιστικό αυτόματο λειτουργεί όπως και το αντίστοιχο ντετερμινιστικό με την διαφορά ότι αντί να μεταβαίνει από μία κατάσταση σε μόνο μία άλλη, μπορεί να μεταβεί και σε περισσότερες από μία καταστάσεις.

Έτσι, ξεκινώντας από την αρχική κατάσταση, q₀ και διαβάζοντας σύμβολα, δεν δημιουργείται μία διαδρομή από κατάσταση σε κατάσταση, αλλά πολλές. Αν μία από αυτές τις διαδρομές καταλήγει σε τελική κατάσταση, η ακολουθία των συμβόλων που διαβάστηκε από το αυτόματο ώστε να καταλήξει εκεί, γίνεται αποδεκτή.

Παράδειγμα

Το αυτόματο του σχήματος αριστερά είναι ένα μη ντεντερμινιστικό πεπερασμένο αυτόματο. Είναι πεπερασμένο, από τη στιγμή που έχει πεπερασμένο αριθμό καταστάσεων (συγκεκριμένα, έχει τρεις καταστάσεις) και είναι μη ντετερμινιστικό από τη στιγμή που τουλάχιστον από μία κατάσταση μπορεί με ένα σύμβολο να μεταβεί σε παραπάνω από μία καταστάσεις. Συγκεκριμένα, από την αρχική κατάσταση Α και με σύμβολο "1" το αυτόματο μεταβαίνει στις καταστάσεις Β και C.

Το σύνολο Q των καταστάσεών του είναι το {Α,Β,C}. Το αλφάβητο εισόδου είναι το σύνολο Σ={0,1}. Η αρχική κατάσταση είναι η q₀=A. Το σύνολο των τελικών καταστάσεων είναι το F={C} και η συνάρτηση μετάβασης περιγράφεται από τις παρακάτω παραστάσεις:

δ(Α,0)=$\emptyset$ , δ(A,1)={B,C}

δ(Β,0)={Α} , δ(Β,1)=$\emptyset$

δ(C,0)={B} , δ(C,1)=$\emptyset$

Ο αντίστοιχος πίνακας για την περιγραφή της συνάρτησης μετάβασης είναι ο παρακάτω.

	0	1
A	$\emptyset$	{B,C}
B	{A}	$\emptyset$
C	{B}	$\emptyset$

Έστω, τώρα, ότι θέλουμε να δούμε αν το συγκεκριμένο αυτόματο αναγνωρίζει τη συμβολοσειρά "1010". Το αυτόματο, πριν διαβαστεί το πρώτο σύμβολο της συμβολοσειράς, βρίσκεται στην αρχική κατάσταση Α. Διαβάζοντας το πρώτο σύμβολο της εισόδου, το "1", μεταβαίνει στις καταστάσεις Β και C, αφού δ(A,1)={B,C}. Βρίσκεται, δηλαδή, και στις δύο καταστάσεις. Διαβάζει το δεύτερο σύμβολο της εισόδου, το "0", και από την Β (στην οποία βρισκόταν πριν) πάει στην A ενώ από C (στην οποία βρισκόταν πριν) πάει στην Β, δηλαδή ${\overline {\delta }}(\{B,C\},1)=\{A,B\}$. Επομένως, μεταβαίνει στις καταστάσεις Α και Β. Στο επόμενο βήμα, διαβάζοντας το επόμενο σύμβολο, το "1", επειδή ${\overline {\delta }}(\{A,B\},1)=\{A,B,C\}=Q$ μεταβαίνει στις A,Β,C, σε όλες τις καταστάσεις του. Διαβάζει το τελευταίο σύμβολο "0" και από την Α, δεν πάει πουθενά ή πάει στο κενό (προσοχή, αυτό δεν σημαίνει ότι παραμένει στην ίδια κατάσταση), από την Β μεταβαίνει στην Α και από την C μεταβαίνει στην Β. Επομένως, το αυτόματο από τις καταστάσεις Α, Β και C με είσοδο το "0" κατέληξε στις καταστάσεις Α και Β. Καμία από αυτές δεν είναι τελική, επομένως, η συμβολοσειρά "1010" απορρίπτεται από το αυτόματο.

Παραλλαγές

• Τα ντετερμινιστικά πεπερασμένα αυτόματα είναι περιπτώσεις μη ντετερμινιστικών πεπερασμένων αυτόματων, όπου από κάθε κατάσταση μπορούμε να μεταβούμε σε μόνο μία άλλη.
• Μια άλλη παραλλαγή των NFA είναι τα μη ντετερμινιστικά αυτόματα με ε-κινήσεις.

Βιβλιογραφία

• M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development, 3:2 (1959) pp. 115–125.
• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. (see section 1.2: Nondeterminism, pp.47–63.)
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 2.)